package quickSort;
/**
 * Created by Administrator on 2017/8/9.
 * 快速排序算法思想：   1、选出一个关键字，
 * 2、由右向左遍历找到小于关键字的，交换关键字和其位置
 * 3、由左向右遍历找到大于关键字的，交换关键字和其位置，
 * 4、继续第二步，直到左右位置相等，完成一次快速排序
 * 待完善：没有对空数组测试！！！
 */

import java.util.Scanner;
import java.lang.Math;

public class Quicksort {
    public static void quickSort(int[] arry, int low, int high, int counter) {

        //判断数组是否为空
        if (arry.length == 0) {
            System.out.println("数组中没有元素！");
        } else {
            int left = low;
            int right = high;
            int key = arry[low];
            //for中left和right的不能写初始值，需要保持每次对其操作的值
            for (; right > left; --right) {
                //从右边遍历找到存在一个数比key小
                if (key > arry[right]) {
                    arry[left] = arry[right];
                    arry[right] = key;                  //必须将key放回坑处
                    for (; left < right; ++left) {

                        if (key < arry[left]) {
                            arry[right] = arry[left];
                            arry[left] = key;
                            //Arry[left]=key;
                            break;
                        }
                    }
                }
                // Arry[left]=key;

            }
            //++counter;

            if (left > low) {
                quickSort(arry, low, left - 1, counter);//左分支继续排序

            }
            if (right < high) {
                quickSort(arry, right + 1, high, counter);//右分支排序。right必须要++

            }
           /*if(low == left && right == high) {
               for (int j = 0; j < Arry.length; ++j)
                   System.out.print(Arry[j] + " ");
               return ;
           }*/
        }

    }

    public static void main(String[] args) {
        int xxx;
        // int k;

        boolean flag = true;
        int counter = 0;                                  //用于统计排序的次数。
        while (flag) {
            System.out.println("\n测试案例如下：" +
                    "\n\t\t\t" + "1、长度为0的数组测试！" +
                    "\n\t\t\t" + "2、长度为5的数组测试！数组为：{3, 23, 4, 6, 87, 25}" +
                    "\n\t\t\t" + "3、长度为10的数组测试！数组为:{3, 23, 4, 6, 87, 25, 2, 4, 9, 15}" +
                    "\n\t\t\t" + "4、自定义长度，随机数组测试！");
            System.out.println("请输入测试案例号：");
            Scanner input = new Scanner(System.in);
            //System.out.println("请输入一个整数：");
            xxx = input.nextInt();
            switch (xxx) {
                ///数组为空和数组长度为0不同，case1需要完善
                case 1:
                    int[] arry1 = new int[]{};
                    // System.out.println("第一次使用空数组测试！");
                    quickSort(arry1, 0, arry1.length, counter);
                    break;
                case 2:
                    //flag = false;
                    int[] arry2 = new int[]{3, 23, 4, 6, 87, 25};
                    //System.out.println("第二次使用一个长度为5的正常数组调用测试！");
                    quickSort(arry2, 0, arry2.length - 1, counter);
                    System.out.println("\n");
                    for (int j = 0; j < arry2.length; ++j)
                        System.out.print(arry2[j] + " ");
                    break;
                case 3:
                    //flag = false;
                    int[] arry3 = new int[]{3, 23, 4, 6, 87, 25, 2, 4, 9, 15};
                    //System.out.println("第三次使用一个长度为10的正常数组调用测试！");
                    quickSort(arry3, 0, arry3.length - 1, counter);
                    for (int j = 0; j < arry3.length; ++j)
                        System.out.print(arry3[j] + " ");
                    break;
                case 4:
                    int n;
                    System.out.println("请输入要排序的个数：");
                    Scanner input2 = new Scanner(System.in);
                    n = input2.nextInt();
                    int[] arry4 = new int[n];
                    System.out.println("排序前的随机数组数据如下：");
                    for (int i = 0; i < n; ++i) {
                        arry4[i] = (int) (Math.random() * 1000);
                        System.out.print(arry4[i] + " ");
                    }
                    System.out.println();
                    System.out.println("排序后随机数组的数据如下：");
                    quickSort(arry4, 0, arry4.length - 1, counter);
                    for (int j = 0; j < arry4.length; ++j)
                        System.out.print(arry4[j] + " ");
                    break;
                default:
                    System.out.println("此案例正在开发中，敬请期待...");
                    break;

            }
        }
    }
}
